1. Field of the Invention
The present invention relates to the optimization of infill survey paths for marine seismic surveys, which are designed to uniformly sample subsurface horizons.
2. Related Art
In seismic surveys, much of the subsurface is not properly sampled due to cable feathering. Thus in order to sample those areas that were missed on the first pass, a seismic vessel is required to make additional passes through a prospect survey area, which significantly increases the time and associated cost to complete a survey. These secondary paths are referred to as xe2x80x9cinfill shootingxe2x80x9d. There are an infinite number of possible paths which the vessel may traverse during the infill portion of the survey. Moreover, in many cases, the optimal infill path is difficult to determine. If optimal infill paths can be identified, however, it significantly lowers the total effort and expense associated with seismic data collection. Thus, there is a need for an efficient means of determining optimal infill paths in seismic surveying.
A large portion of marine data collection is devoted to the infill portion of a prospect. The infill may take up to several weeks to complete. Since the typical operating costs of a seismic vessel exceed $50,000 per day, the infill data is very expensive. Thus, optimal infill shooting would result in an enormous cost savings for surveying each seismic prospect. These large cost reductions would provide a competitive advantage in the marine data collection market.
There are many known techniques that have been utilized in an attempt to optimize a given set of data. For example, genetic algorithms, simulated annealing, cellular automata, and calculus-based algorithms have all been used to optimize different physical quantities. Many known procedures have been developed for finding the shortest route between two points. One of the more useful techniques was advanced by Lee. Lee""s algorithm is able to find the shortest path between two points on a rectangular grid containing obstacles. In Lee""s scheme, movement is restricted to the vertical and horizontal directions. Referring to FIG. 1, a shortest path route is developed in the following manner: Starting with a xe2x80x9cgoalxe2x80x9d cell, a xe2x80x9c1xe2x80x9d is placed in all adjacent empty cells as shown in FIG. 1. Next, a xe2x80x9c2xe2x80x9d is placed in any cell which borders a cell containing a value of xe2x80x9c1xe2x80x9d. This process continues until the xe2x80x9cstartxe2x80x9d cell is reached.
The optimal path is determined by beginning at the xe2x80x9cstartxe2x80x9d cell 100 and moving to the bordering cell 102 with the lowest numeric value. Note that during the path generation phase, diagonal moves are permitted, however, in some cases they may not be allowed. For example, a cab driver must keep his vehicle on paved roads and may not take a diagonal path through private property. The optimal path 103 for the preceding example is shown in FIG. 2.
Removing one of the object cells 104, results in multiple path solutions 105, 106, however, as shown in FIG. 3. When equal cost solutions exist, the problem is referred to as a digital indiscrimination problem. Each separate path is referred to as a geodesic. In this example only two equal paths exist. A larger map containing several thousand cells could yield dozens of equivalent geodesics. At first glance, the digital indiscrimination issue may not appear to be problematic, however, in many cases one path may be preferred over another. For example, a straighter path may be favored over one that has several turns.
Moreover, the shortest path does not always mean it is also the least cost path. Consider the problem of a traveling salesman attempting to drive to the airport on the other side of town. The salesman has the choice of taking the long freeway route around town or the shorter drive, straight through the middle of the city. The short route through town might enable the salesman to catch an earlier flight and make additional sales, however, if there are traffic jams in the city, getting stuck in traffic could cause the salesman to miss both flights.
In the traveling salesman example the least cost path depends on the time of day the salesman wants to drive to the airport. In general, determining an optimal route depends on a number of factors. Unlike the shortest path algorithm, the least cost technique requires an initial xe2x80x9ccost mapxe2x80x9d. Cost maps are generated by subdividing a map of an area into an array of cells. A cost value is assigned to each map cell. Cost values typically represent the cost incurred in moving from one map cell to another. For the two dimensional salesman problem, the freeway path would be assigned a low cost value and areas of high traffic density in the city would be assigned a higher cost value. Obstacles such as lakes, rivers, or canyons would be assigned very large cost values. By correctly processing the resulting cost map, the salesman would be able to generate a xe2x80x9cbest cost mapxe2x80x9d. This map will enable him to determine the optimal route to the airport.
If all non-object cells in a cost map are equally weighted, the resulting best-cost map is equivalent to a shortest path map. For example, consider the least cost map shown in FIG. 4. Each entry in the example of FIG. 4 represents the cost of moving from one cell to another. All cells in the best-cost map are initialized with large integers. To generate a final best cost BC map, we can utilize the Stiles and Glickstein method (see P. N. Stiles and I. S. Glickstein [1994], xe2x80x9cHighly Parallelizable Route Planner Bases on Cellular Automata Algorithms.xe2x80x9d IBM J. RES. Develop. Vol. 38 No. 2 March 1994, pp. 167-181). The Stiles and Glickstein method begins by setting the goal cell in the BC map equal to zero and adds the map cost of an adjacent cell (MCj). The cost for moving to cell BCj is therefore calculated as:
cost=BCi+MCj
where
BCi=best cost value for current cell I
MCj=map cost of cell adjacent to current cell
The cost for moving to another cell adjacent cell, BC is then calculated. If the resulting cost is less than the BCj, the map cost is replaced with the new value, i.e., BCj=cost. Since the value for BCj has changed, the cell is placed on a xe2x80x9cTO DOxe2x80x9d list for further processing. The same procedure is followed for all adjacent cells. When all bordering cells have been processed, the cell at the top of the TODO list is then processed in a similar manner. The cells on the TODO list are processed until the TODO list is empty. The pseudo code developed for this process is shown below in table 1 (see, P. N. Stiles, I. S. Glickstein, [1994] pp. 167-181).
The final BC map is identical to the map shown in FIG. 2. Now, consider a slightly modified BC map as shown in FIG. 5. If the least cost algorithm is applied to this BC map, a completely different path 107 is generated, as shown in FIG. 6. The path is now longer than the path calculated by the shortest route algorithm, however, the travel cost is less.
In the above examples, a cost was assigned to each cell. These costs may be a function of many different variables. It is possible to create n-dimensional least cost models. For example, time may be an additional dimension. The number of cells considered thus far in the examples is relatively small. Applications involving real maps, having thousands of individual cells makes finding a least cost route a substantially complex and formidable task. Thus, there is a need for an efficient method of determining a optimal path for infill shooting a seismic prospect area
The present invention provides an efficient method for determining optimal paths using multiple offset cost maps. In the present invention, cellular automata are utilized to determine optimal paths for the infill portion of a seismic survey cell values are represented as potentials. The fundamental concept of the xe2x80x9cleast cost pathxe2x80x9d is enhanced and applied to marine seismic operation to optimize seismic vessel paths during infill shooting. The inventor knows of no prior method, which attempts to find an optimal route for a seismic vessel using multiple cost maps.